package com.kevinkk.graph;

/**
 * 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
 * 请你实现 Trie 类：
 * void insert(String word) 向前缀树中插入字符串 word 。
 * boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
 * boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
 */

public class ImplementTriePrefixTree {
    // 每个节点对应有 26 个孩子，以及一个标识位、标识是否是结尾
    class Node{
        Node[] children = new Node[26];
        boolean isEnd = false;
    }

    class Trie {
        Node root = new Node();                 // 前缀树的根节点

        public void insert(String word) {
            char[] c = word.toCharArray();
            Node cur = root;                    // 从根节点进行插入
            for(int i = 0; i < c.length; i++){
                int index = c[i] - 'a';         // 在对应索引插入，a 插入第 0 个位置，以此类推
                if(cur.children[index] == null) // 如果要插入的地方为空，则需要继续向下创建
                        cur.children[index] = new Node();
                cur = cur.children[index];      // 继续向下遍历
            }
            cur.isEnd = true;                   // 最后一个节点的标识位为 true
        }

        private Node search(char[] c){
            Node cur = root;            // 从根节点进行搜索
            for(int i = 0; i < c.length; i++){
                int index = c[i] - 'a';
                // 如果没有查到直接返回空
                if(cur.children[index] == null) return null;
                cur = cur.children[index];
            }
            return cur;
        }

        public boolean search(String word) {
            Node node = search(word.toCharArray());
            return node == null ? false : node.isEnd;   // 必须查到、且是最后一个字符
        }

        public boolean startsWith(String prefix) {
            return search(prefix.toCharArray()) != null;// 不为空就代表查到了前缀
        }
    }
}
